package leetcode.code0637;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import leetcode.helper.tree.TreeNode;

/**
 * 执行用时：2 ms, 在所有 Java 提交中击败了93.35%的用户
 * 
 * 内存消耗：43 MB, 在所有 Java 提交中击败了48.40%的用户
 * 
 * 通过测试用例：66 / 66
 */
public class Solution {
	public List<Double> averageOfLevels(TreeNode root) {
		List<Double> ans = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int cnt = queue.size();
			double sum = 0;
			for (int i = 0; i < cnt; i++) {
				TreeNode cur = queue.poll();
				sum += cur.val;
				if (cur.left != null) {
					queue.add(cur.left);
				}
				if (cur.right != null) {
					queue.add(cur.right);
				}
			}
			ans.add(sum / cnt);
		}

		return ans;
	}
}
